#include <stdio.h>

#define N 7
/**
 * File: Exercise1004.c
 * -------------------------------------------------------
 * 1.4 Show the contents of the `id` array after each `union` operation when you use the `quick-find` algorithm (Program 1.1) to solve the connectivity problem for the sequence 0-2, 1-4, 2-5, 3-6, 0-4, 6-0, and 1-3.
 * Also give the number of times the program accesses the `id` array for each input pair.
 * -------------------------------------------------------
 * 输入
 * 0 2 1 4 2 5 3 6 0 4 6 0 1 3
 * -------------------------------------------------------
 * 出处：[QuickFind.c](https://gitcode.com/haoly1989/books/blob/main/AlgorithmsInC/examples/chapter1/QuickFind.c)
 */
int main(int argc, char **argv){
    int i, p, q, t;
    int id[N];

    //初始化id数组值为索引值
    for (i = 0; i < N; i++) {
        id[i] = i;
    }

    while (scanf("%d %d\n", &p, &q) == 2) {
        int count = 0;//对每个输入对，统计访问数组的次数
        count+=2;
        if (id[p]==id[q]) {
            continue;
        }
        
        t = id[p];
        count++;
        for (i = 0; i < N; i++) {
            count++;
            if (id[i] == t) {
                id[i] = id[q];
                count+=2;
            }
        }
        // printf("%d %d\n", p, q);
        for (int j = 0; j < N; j++) {
            printf("%d ", id[j]);
        }
        printf("\n");

        printf("%d-%d access array %d times\n", p, q, count);
    }
    return 0;
}

//每次union后，id数组的内容
// 2 1 2 3 4 5 6 
// 0-2 access array 12 times
// 2 4 2 3 4 5 6 
// 1-4 access array 12 times
// 5 4 5 3 4 5 6 
// 2-5 access array 14 times
// 5 4 5 6 4 5 6 
// 3-6 access array 12 times
// 4 4 4 6 4 4 6 
// 0-4 access array 16 times
// 4 4 4 4 4 4 4 
// 6-0 access array 14 times